package day03;

import java.util.HashMap;

/**
 * @author ZJX
 * @version 1.0
 * @descption
 * @since 2025/10/12 20:22
 */
public class A {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0] >= target ? 1 : 0;
        int left = 0;
        int sum = 0;
        int ret = Integer.MAX_VALUE;
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                ret = Math.min(ret, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return ret == Integer.MAX_VALUE ? 0 : ret;
    }

    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0;
        int ret = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (map.containsKey(ch)) {
                left = Math.max(left, map.get(ch) + 1);
            }
            map.put(ch, i);
            ret = Math.max(ret, i - left + 1);
        }
        return ret;
    }

    public String minWindow(String s, String t) {
        if (t.isEmpty()) {
            return "";
        }
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int len = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int start = 0;
        int size = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            if (need.containsKey(ch)) {
                window.put(ch, window.getOrDefault(ch, 0) + 1);
                if (window.get(ch).equals(need.get(ch))) {
                    size++;
                }
            }
            right++;
            while (size == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        size--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    public int subarraySum(int[] nums, int k) {
//        连续子数组的和   --->  前缀和
//        前缀和的核心价值：将 “子数组和” 转化为 “前缀和的差”
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0;
        int count = 0;
        for (int num : nums) {
            sum += num;
            // 检查是否存在某个前缀和使得 sum - preSum == k
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }

            // 更新当前前缀和出现次数
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

